package 队列与栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

//最大频率栈
//https://leetcode.cn/problems/maximum-frequency-stack/
class 最大频率栈 {
    // 记录 FreqStack 中元素的最大频率
    int maxFreq = 0;
    //存储每个val的频率
    Map<Integer, Integer> freMap = new HashMap<>();
    //存储每个频率对应的站
    Map<Integer, Stack<Integer>> freStackMap = new HashMap<>();

    public void push(int val) {
        //更新对应值的频率
        int freq = freMap.getOrDefault(val, 0) + 1;
        freMap.put(val, freq);
        //获取频率对应的栈
        freStackMap.putIfAbsent(freq, new Stack<>());
        //将新加的val存进对应频率的栈
        freStackMap.get(freq).push(val);
        //更新最大频率
        maxFreq = Math.max(maxFreq, freq);
    }

    public int pop() {
        //获取当前最大频率的栈
        Stack<Integer> stack = freStackMap.get(maxFreq);
        //获取当前最大频率的栈的栈顶元素，即它是离栈顶最近频率最大的
        Integer topVal = stack.pop();
        //更新对应值出现的频率
        freMap.put(topVal, freMap.get(topVal) - 1);
        //如果最大频率的栈为空了，表示该频率已经没有对应的元素，即最大频率减一
        if (stack.isEmpty()) {
            maxFreq--;
        }
        return topVal;
    }

    public static void main(String[] args) {
        最大频率栈 freqStack1 = new 最大频率栈();
        freqStack1.push(5);
        freqStack1.push(7);
        freqStack1.push(5);
        freqStack1.push(7);
        freqStack1.push(4);
        freqStack1.push(5);
        freqStack1.pop();
        freqStack1.pop();
        freqStack1.pop();
        freqStack1.pop();
    }
}

